home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / nt / emacssrc.zip / EMACSSRC.TAR / emacs-19.17 / src / intervals.c < prev    next >
C/C++ Source or Header  |  1993-10-07  |  47KB  |  1,676 lines
  1. /* Code for doing intervals.
  2.    Copyright (C) 1993 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU Emacs.
  5.  
  6. GNU Emacs is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. GNU Emacs is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU Emacs; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. /* NOTES:
  22.  
  23.    Have to ensure that we can't put symbol nil on a plist, or some
  24.    functions may work incorrectly.
  25.  
  26.    An idea:  Have the owner of the tree keep count of splits and/or
  27.    insertion lengths (in intervals), and balance after every N.
  28.  
  29.    Need to call *_left_hook when buffer is killed.
  30.  
  31.    Scan for zero-length, or 0-length to see notes about handling
  32.    zero length interval-markers.
  33.  
  34.    There are comments around about freeing intervals.  It might be
  35.    faster to explicitly free them (put them on the free list) than
  36.    to GC them.
  37.  
  38. */
  39.  
  40.  
  41. #include "config.h"
  42. #include "lisp.h"
  43. #include "intervals.h"
  44. #include "buffer.h"
  45.  
  46. #ifdef STDC_HEADERS
  47. #include <stdlib.h>
  48. #endif
  49. #include "intervals_p.h"
  50. static void merge_properties _P_((register INTERVAL source,
  51.                                   register INTERVAL target));
  52. static void inc_interval_count _P_((INTERVAL i));
  53. static INTERVAL root_interval _P_((INTERVAL interval));
  54. static INTERVAL rotate_right _P_((INTERVAL interval));
  55. static INTERVAL rotate_left _P_((INTERVAL interval));
  56. static INTERVAL adjust_intervals_for_insertion _P_((INTERVAL tree,
  57.                                                     int position, int length));
  58. static INTERVAL adjust_intervals_for_insertion _P_((INTERVAL tree,
  59.                                                     int position, int length));
  60. static INTERVAL delete_node _P_((register INTERVAL i));
  61. static int interval_deletion_adjustment _P_((register INTERVAL tree,
  62.                                              register int from,
  63.                                              register int amount));
  64. static void adjust_intervals_for_deletion _P_((struct buffer *buffer,
  65.                                                int start, int length));
  66. static INTERVAL reproduce_tree _P_((INTERVAL source, INTERVAL parent));
  67. static INTERVAL make_new_interval _P_((INTERVAL intervals, int start,
  68.                                        int length));
  69. static void call_mod_hooks _P_((Lisp_Object list, Lisp_Object start,
  70.                                 Lisp_Object end));
  71. static INTERVAL balance_an_interval _P_((INTERVAL i));
  72.  
  73. /* The rest of the file is within this conditional. */
  74. #ifdef USE_TEXT_PROPERTIES
  75.  
  76. /* Factor for weight-balancing interval trees. */
  77. Lisp_Object interval_balance_threshold;
  78.  
  79. /* Utility functions for intervals. */
  80.  
  81.  
  82. /* Create the root interval of some object, a buffer or string. */
  83.  
  84. INTERVAL
  85. create_root_interval (parent)
  86.      Lisp_Object parent;
  87. {
  88.   INTERVAL new = make_interval ();
  89.  
  90.   if (XTYPE (parent) == Lisp_Buffer)
  91.     {
  92.       new->total_length = (BUF_Z (XBUFFER (parent))
  93.                - BUF_BEG (XBUFFER (parent)));
  94.       XBUFFER (parent)->intervals = new;
  95.     }
  96.   else if (XTYPE (parent) == Lisp_String)
  97.     {
  98.       new->total_length = XSTRING (parent)->size;
  99.       XSTRING (parent)->intervals = new;
  100.     }
  101.  
  102.   new->parent = (INTERVAL) parent;
  103.   new->position = 1;
  104.  
  105.   return new;
  106. }
  107.  
  108. /* Make the interval TARGET have exactly the properties of SOURCE */
  109.  
  110. void
  111. copy_properties (source, target)
  112.      register INTERVAL source, target;
  113. {
  114.   if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
  115.     return;
  116.  
  117.   COPY_INTERVAL_CACHE (source, target);
  118.   target->plist = Fcopy_sequence (source->plist);
  119. }
  120.  
  121. /* Merge the properties of interval SOURCE into the properties
  122.    of interval TARGET.  That is to say, each property in SOURCE
  123.    is added to TARGET if TARGET has no such property as yet.  */
  124.  
  125. static void
  126. merge_properties (source, target)
  127.      register INTERVAL source, target;
  128. {
  129.   register Lisp_Object o, sym, val;
  130.  
  131.   if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
  132.     return;
  133.  
  134.   MERGE_INTERVAL_CACHE (source, target);
  135.  
  136.   o = source->plist;
  137.   while (! EQ (o, Qnil))
  138.     {
  139.       sym = Fcar (o);
  140.       val = Fmemq (sym, target->plist);
  141.  
  142.       if (NILP (val))
  143.     {
  144.       o = Fcdr (o);
  145.       val = Fcar (o);
  146.       target->plist = Fcons (sym, Fcons (val, target->plist));
  147.       o = Fcdr (o);
  148.     }
  149.       else
  150.     o = Fcdr (Fcdr (o));
  151.     }
  152. }
  153.  
  154. /* Return 1 if the two intervals have the same properties,
  155.    0 otherwise. */
  156.  
  157. int
  158. intervals_equal (i0, i1)
  159.      INTERVAL i0, i1;
  160. {
  161.   register Lisp_Object i0_cdr, i0_sym, i1_val;
  162.   register i1_len;
  163.  
  164.   if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
  165.     return 1;
  166.  
  167.   if (DEFAULT_INTERVAL_P (i0) || DEFAULT_INTERVAL_P (i1))
  168.     return 0;
  169.  
  170.   i1_len = XFASTINT (Flength (i1->plist));
  171.   if (i1_len & 0x1)        /* Paranoia -- plists are always even */
  172.     abort ();
  173.   i1_len /= 2;
  174.   i0_cdr = i0->plist;
  175.   while (!NILP (i0_cdr))
  176.     {
  177.       /* Lengths of the two plists were unequal */
  178.       if (i1_len == 0)
  179.     return 0;
  180.  
  181.       i0_sym = Fcar (i0_cdr);
  182.       i1_val = Fmemq (i0_sym, i1->plist);
  183.  
  184.       /* i0 has something i1 doesn't */
  185.       if (EQ (i1_val, Qnil))
  186.     return 0;
  187.  
  188.       /* i0 and i1 both have sym, but it has different values in each */
  189.       i0_cdr = Fcdr (i0_cdr);
  190.       if (! EQ (i1_val, Fcar (i0_cdr)))
  191.     return 0;
  192.  
  193.       i0_cdr = Fcdr (i0_cdr);
  194.       i1_len--;
  195.     }
  196.  
  197.   /* Lengths of the two plists were unequal */
  198.   if (i1_len > 0)
  199.     return 0;
  200.  
  201.   return 1;
  202. }
  203.  
  204. static int icount;
  205. static int idepth;
  206. static int zero_length;
  207.  
  208. /* Traverse an interval tree TREE, performing FUNCTION on each node.
  209.    Pass FUNCTION two args: an interval, and ARG.  */
  210.  
  211. void
  212. traverse_intervals (tree, position, depth, function, arg)
  213.      INTERVAL tree;
  214.      int position, depth;
  215.      void (* function) _P_((INTERVAL tree, Lisp_Object arg));
  216.      Lisp_Object arg;
  217. {
  218.   if (NULL_INTERVAL_P (tree))
  219.     return;
  220.  
  221.   traverse_intervals (tree->left, position, depth + 1, function, arg);
  222.   position += LEFT_TOTAL_LENGTH (tree);
  223.   tree->position = position;
  224.   (*function) (tree, arg);
  225.   position += LENGTH (tree);
  226.   traverse_intervals (tree->right, position, depth + 1,  function, arg);
  227. }
  228.  
  229. #if 0
  230. /* These functions are temporary, for debugging purposes only. */
  231.  
  232. INTERVAL search_interval, found_interval;
  233.  
  234. void
  235. check_for_interval (i)
  236.      register INTERVAL i;
  237. {
  238.   if (i == search_interval)
  239.     {
  240.       found_interval = i;
  241.       icount++;
  242.     }
  243. }
  244.  
  245. INTERVAL
  246. search_for_interval (i, tree)
  247.      register INTERVAL i, tree;
  248. {
  249.   icount = 0;
  250.   search_interval = i;
  251.   found_interval = NULL_INTERVAL;
  252.   traverse_intervals (tree, 1, 0, &check_for_interval, Qnil);
  253.   return found_interval;
  254. }
  255.  
  256. static void
  257. inc_interval_count (i)
  258.      INTERVAL i;
  259. {
  260.   icount++;
  261.   if (LENGTH (i) == 0)
  262.     zero_length++;
  263.   if (depth > idepth)
  264.     idepth = depth;
  265. }
  266.  
  267. int
  268. count_intervals (i)
  269.      register INTERVAL i;
  270. {
  271.   icount = 0;
  272.   idepth = 0;
  273.   zero_length = 0;
  274.   traverse_intervals (i, 1, 0, &inc_interval_count, Qnil);
  275.  
  276.   return icount;
  277. }
  278.  
  279. static INTERVAL
  280. root_interval (interval)
  281.      INTERVAL interval;
  282. {
  283.   register INTERVAL i = interval;
  284.  
  285.   while (! ROOT_INTERVAL_P (i))
  286.     i = i->parent;
  287.  
  288.   return i;
  289. }
  290. #endif
  291.  
  292. /* Assuming that a left child exists, perform the following operation:
  293.  
  294.      A          B
  295.     / \         / \
  296.    B       =>       A
  297.   / \           / \
  298.      c          c
  299. */
  300.  
  301. static INTERVAL
  302. rotate_right (interval)
  303.      INTERVAL interval;
  304. {
  305.   INTERVAL i;
  306.   INTERVAL B = interval->left;
  307.   int len = LENGTH (interval);
  308.  
  309.   /* Deal with any Parent of A;  make it point to B. */
  310.   if (! ROOT_INTERVAL_P (interval))
  311.     if (AM_LEFT_CHILD (interval))
  312.       interval->parent->left = interval->left;
  313.     else
  314.       interval->parent->right = interval->left;
  315.   interval->left->parent = interval->parent;
  316.  
  317.   /* B gets the same length as A, since it get A's position in the tree. */
  318.   interval->left->total_length = interval->total_length;
  319.  
  320.   /* B becomes the parent of A. */
  321.   i = interval->left->right;
  322.   interval->left->right = interval;
  323.   interval->parent = interval->left;
  324.  
  325.   /* A gets c as left child. */
  326.   interval->left = i;
  327.   if (! NULL_INTERVAL_P (i))
  328.     i->parent = interval;
  329.   interval->total_length = (len + LEFT_TOTAL_LENGTH (interval)
  330.                 + RIGHT_TOTAL_LENGTH (interval));
  331.  
  332.   return B;
  333. }
  334.  
  335. /* Assuming that a right child exists, perform the following operation:
  336.  
  337.     A               B   
  338.    / \               / \  
  339.       B       =>     A
  340.      / \         / \    
  341.     c               c
  342. */
  343.  
  344. static INTERVAL
  345. rotate_left (interval)
  346.      INTERVAL interval;
  347. {
  348.   INTERVAL i;
  349.   INTERVAL B = interval->right;
  350.   int len = LENGTH (interval);
  351.  
  352.   /* Deal with the parent of A. */
  353.   if (! ROOT_INTERVAL_P (interval))
  354.     if (AM_LEFT_CHILD (interval))
  355.       interval->parent->left = interval->right;
  356.     else
  357.       interval->parent->right = interval->right;
  358.   interval->right->parent = interval->parent;
  359.  
  360.   /* B must have the same total length of A. */
  361.   interval->right->total_length = interval->total_length;
  362.  
  363.   /* Make B the parent of A */
  364.   i = interval->right->left;
  365.   interval->right->left = interval;
  366.   interval->parent = interval->right;
  367.  
  368.   /* Make A point to c */
  369.   interval->right = i;
  370.   if (! NULL_INTERVAL_P (i))
  371.     i->parent = interval;
  372.   interval->total_length = (len + LEFT_TOTAL_LENGTH (interval)
  373.                 + RIGHT_TOTAL_LENGTH (interval));
  374.  
  375.   return B;
  376. }
  377.  
  378. /* Split INTERVAL into two pieces, starting the second piece at
  379.    character position OFFSET (counting from 0), relative to INTERVAL.
  380.    INTERVAL becomes the left-hand piece, and the right-hand piece
  381.    (second, lexicographically) is returned.
  382.  
  383.    The size and position fields of the two intervals are set based upon
  384.    those of the original interval.  The property list of the new interval
  385.    is reset, thus it is up to the caller to do the right thing with the
  386.    result.
  387.  
  388.    Note that this does not change the position of INTERVAL;  if it is a root,
  389.    it is still a root after this operation. */
  390.  
  391. INTERVAL
  392. split_interval_right (interval, offset)
  393.      INTERVAL interval;
  394.      int offset;
  395. {
  396.   INTERVAL new = make_interval ();
  397.   int position = interval->position;
  398.   int new_length = LENGTH (interval) - offset;
  399.  
  400.   new->position = position + offset;
  401.   new->parent = interval;
  402.  
  403.   if (LEAF_INTERVAL_P (interval) || NULL_RIGHT_CHILD (interval))
  404.     {
  405.       interval->right = new;
  406.       new->total_length = new_length;
  407.  
  408.       return new;
  409.     }
  410.  
  411.   /* Insert the new node between INTERVAL and its right child. */
  412.   new->right = interval->right;
  413.   interval->right->parent = new;
  414.   interval->right = new;
  415.  
  416.   new->total_length = new_length + new->right->total_length;
  417.  
  418.   return new;
  419. }
  420.  
  421. /* Split INTERVAL into two pieces, starting the second piece at
  422.    character position OFFSET (counting from 0), relative to INTERVAL.
  423.    INTERVAL becomes the right-hand piece, and the left-hand piece
  424.    (first, lexicographically) is returned.
  425.  
  426.    The size and position fields of the two intervals are set based upon
  427.    those of the original interval.  The property list of the new interval
  428.    is reset, thus it is up to the caller to do the right thing with the
  429.    result.
  430.  
  431.    Note that this does not change the position of INTERVAL;  if it is a root,
  432.    it is still a root after this operation. */
  433.  
  434. INTERVAL
  435. split_interval_left (interval, offset)
  436.      INTERVAL interval;
  437.      int offset;
  438. {
  439.   INTERVAL new = make_interval ();
  440.   int position = interval->position;
  441.   int new_length = offset;
  442.  
  443.   new->position = interval->position;
  444.   interval->position = interval->position + offset;
  445.   new->parent = interval;
  446.  
  447.   if (NULL_LEFT_CHILD (interval))
  448.     {
  449.       interval->left = new;
  450.       new->total_length = new_length;
  451.  
  452.       return new;
  453.     }
  454.  
  455.   /* Insert the new node between INTERVAL and its left child. */
  456.   new->left = interval->left;
  457.   new->left->parent = new;
  458.   interval->left = new;
  459.   new->total_length = new_length + LEFT_TOTAL_LENGTH (new);
  460.  
  461.   return new;
  462. }
  463.  
  464. /* Find the interval containing text position POSITION in the text
  465.    represented by the interval tree TREE.  POSITION is a buffer
  466.    position; the earliest position is 1.  If POSITION is at the end of
  467.    the buffer, return the interval containing the last character.
  468.  
  469.    The `position' field, which is a cache of an interval's position,
  470.    is updated in the interval found.  Other functions (e.g., next_interval)
  471.    will update this cache based on the result of find_interval. */
  472.  
  473. INLINE INTERVAL
  474. find_interval (tree, position)
  475.      register INTERVAL tree;
  476.      register int position;
  477. {
  478.   /* The distance from the left edge of the subtree at TREE
  479.                     to POSITION.  */
  480.   register int relative_position = position - BEG;
  481.  
  482.   if (NULL_INTERVAL_P (tree))
  483.     return NULL_INTERVAL;
  484.  
  485.   if ((unsigned)relative_position > TOTAL_LENGTH (tree))
  486.     abort ();            /* Paranoia */
  487.  
  488.   while (1)
  489.     {
  490.       if ((unsigned)relative_position < LEFT_TOTAL_LENGTH (tree))
  491.     {
  492.       tree = tree->left;
  493.     }
  494.       else if (! NULL_RIGHT_CHILD (tree)
  495.            && (unsigned)relative_position >= (TOTAL_LENGTH (tree)
  496.                     - RIGHT_TOTAL_LENGTH (tree)))
  497.     {
  498.       relative_position -= (TOTAL_LENGTH (tree)
  499.                 - RIGHT_TOTAL_LENGTH (tree));
  500.       tree = tree->right;
  501.     }
  502.       else
  503.     {
  504.       tree->position =
  505.         (position - relative_position /* the left edge of *tree */
  506.          + LEFT_TOTAL_LENGTH (tree)); /* the left edge of this interval */
  507.  
  508.       return tree;
  509.     }
  510.     }
  511. }
  512.  
  513. /* Find the succeeding interval (lexicographically) to INTERVAL.
  514.    Sets the `position' field based on that of INTERVAL (see
  515.    find_interval). */
  516.  
  517. INTERVAL
  518. next_interval (interval)
  519.      register INTERVAL interval;
  520. {
  521.   register INTERVAL i = interval;
  522.   register int next_position;
  523.  
  524.   if (NULL_INTERVAL_P (i))
  525.     return NULL_INTERVAL;
  526.   next_position = interval->position + LENGTH (interval);
  527.  
  528.   if (! NULL_RIGHT_CHILD (i))
  529.     {
  530.       i = i->right;
  531.       while (! NULL_LEFT_CHILD (i))
  532.     i = i->left;
  533.  
  534.       i->position = next_position;
  535.       return i;
  536.     }
  537.  
  538.   while (! NULL_PARENT (i))
  539.     {
  540.       if (AM_LEFT_CHILD (i))
  541.     {
  542.       i = i->parent;
  543.       i->position = next_position;
  544.       return i;
  545.     }
  546.  
  547.       i = i->parent;
  548.     }
  549.  
  550.   return NULL_INTERVAL;
  551. }
  552.  
  553. /* Find the preceding interval (lexicographically) to INTERVAL.
  554.    Sets the `position' field based on that of INTERVAL (see
  555.    find_interval). */
  556.  
  557. INTERVAL
  558. previous_interval (interval)
  559.      register INTERVAL interval;
  560. {
  561.   register INTERVAL i;
  562.  
  563.   if (NULL_INTERVAL_P (interval))
  564.     return NULL_INTERVAL;
  565.  
  566.   if (! NULL_LEFT_CHILD (interval))
  567.     {
  568.       i = interval->left;
  569.       while (! NULL_RIGHT_CHILD (i))
  570.     i = i->right;
  571.  
  572.       i->position = interval->position - LENGTH (i);
  573.       return i;
  574.     }
  575.  
  576.   i = interval;
  577.   while (! NULL_PARENT (i))
  578.     {
  579.       if (AM_RIGHT_CHILD (i))
  580.     {
  581.       i = i->parent;
  582.  
  583.       i->position = interval->position - LENGTH (i);
  584.       return i;
  585.     }
  586.       i = i->parent;
  587.     }
  588.  
  589.   return NULL_INTERVAL;
  590. }
  591.  
  592. #if 0
  593. /* Traverse a path down the interval tree TREE to the interval
  594.    containing POSITION, adjusting all nodes on the path for
  595.    an addition of LENGTH characters.  Insertion between two intervals
  596.    (i.e., point == i->position, where i is second interval) means
  597.    text goes into second interval.
  598.  
  599.    Modifications are needed to handle the hungry bits -- after simply
  600.    finding the interval at position (don't add length going down),
  601.    if it's the beginning of the interval, get the previous interval
  602.    and check the hugry bits of both.  Then add the length going back up
  603.    to the root. */
  604.  
  605. static INTERVAL
  606. adjust_intervals_for_insertion (tree, position, length)
  607.      INTERVAL tree;
  608.      int position, length;
  609. {
  610.   register int relative_position;
  611.   register INTERVAL this;
  612.  
  613.   if (TOTAL_LENGTH (tree) == 0)    /* Paranoia */
  614.     abort ();
  615.  
  616.   /* If inserting at point-max of a buffer, that position
  617.      will be out of range */
  618.   if (position > TOTAL_LENGTH (tree))
  619.     position = TOTAL_LENGTH (tree);
  620.   relative_position = position;
  621.   this = tree;
  622.  
  623.   while (1)
  624.     {
  625.       if (relative_position <= LEFT_TOTAL_LENGTH (this))
  626.     {
  627.       this->total_length += length;
  628.       this = this->left;
  629.     }
  630.       else if (relative_position > (TOTAL_LENGTH (this)
  631.                     - RIGHT_TOTAL_LENGTH (this)))
  632.     {
  633.       relative_position -= (TOTAL_LENGTH (this)
  634.                 - RIGHT_TOTAL_LENGTH (this));
  635.       this->total_length += length;
  636.       this = this->right;
  637.     }
  638.       else
  639.     {
  640.       /* If we are to use zero-length intervals as buffer pointers,
  641.          then this code will have to change. */
  642.       this->total_length += length;
  643.       this->position = LEFT_TOTAL_LENGTH (this)
  644.                        + position - relative_position + 1;
  645.       return tree;
  646.     }
  647.     }
  648. }
  649. #endif
  650.  
  651. /* Effect an adjustment corresponding to the addition of LENGTH characters
  652.    of text.  Do this by finding the interval containing POSITION in the
  653.    interval tree TREE, and then adjusting all of it's ancestors by adding
  654.    LENGTH to them.
  655.  
  656.    If POSITION is the first character of an interval, meaning that point
  657.    is actually between the two intervals, make the new text belong to
  658.    the interval which is "sticky".
  659.  
  660.    If both intervals are "sticky", then make them belong to the left-most
  661.    interval.  Another possibility would be to create a new interval for
  662.    this text, and make it have the merged properties of both ends. */
  663.  
  664. static INTERVAL
  665. adjust_intervals_for_insertion (tree, position, length)
  666.      INTERVAL tree;
  667.      int position, length;
  668. {
  669.   register INTERVAL i;
  670.  
  671.   if (TOTAL_LENGTH (tree) == 0)    /* Paranoia */
  672.     abort ();
  673.  
  674.   /* If inserting at point-max of a buffer, that position will be out
  675.      of range.  Remember that buffer positions are 1-based.  */
  676.   if ((unsigned)position > BEG + TOTAL_LENGTH (tree))
  677.     position = BEG + TOTAL_LENGTH (tree);
  678.  
  679.   i = find_interval (tree, position);
  680.   /* If we are positioned between intervals, check the stickiness of
  681.      both of them. */
  682.   if ((unsigned)position == i->position
  683.       && position != BEG)
  684.     {
  685.       register INTERVAL prev = previous_interval (i);
  686.  
  687.       /* If both intervals are sticky here, then default to the
  688.          left-most one.  But perhaps we should create a new
  689.      interval here instead... */
  690.       if (END_STICKY_P (prev) || ! FRONT_STICKY_P (i))
  691.     i = prev;
  692.     }
  693.  
  694.   while (! NULL_INTERVAL_P (i))
  695.     {
  696.       i->total_length += length;
  697.       i = i->parent;
  698.     }
  699.  
  700.   return tree;
  701. }
  702.  
  703. /* Delete an node I from its interval tree by merging its subtrees
  704.    into one subtree which is then returned.  Caller is responsible for
  705.    storing the resulting subtree into its parent. */
  706.  
  707. static INTERVAL
  708. delete_node (i)
  709.      register INTERVAL i;
  710. {
  711.   register INTERVAL migrate, this;
  712.   register int migrate_amt;
  713.  
  714.   if (NULL_INTERVAL_P (i->left))
  715.     return i->right;
  716.   if (NULL_INTERVAL_P (i->right))
  717.     return i->left;
  718.  
  719.   migrate = i->left;
  720.   migrate_amt = i->left->total_length;
  721.   this = i->right;
  722.   this->total_length += migrate_amt;
  723.   while (! NULL_INTERVAL_P (this->left))
  724.     {
  725.       this = this->left;
  726.       this->total_length += migrate_amt;
  727.     }
  728.   this->left = migrate;
  729.   migrate->parent = this;
  730.  
  731.   return i->right;
  732. }
  733.  
  734. /* Delete interval I from its tree by calling `delete_node'
  735.    and properly connecting the resultant subtree.
  736.  
  737.    I is presumed to be empty; that is, no adjustments are made
  738.    for the length of I. */
  739.  
  740. void
  741. delete_interval (i)
  742.      register INTERVAL i;
  743. {
  744.   register INTERVAL parent;
  745.   int amt = LENGTH (i);
  746.  
  747.   if (amt > 0)            /* Only used on zero-length intervals now. */
  748.     abort ();
  749.  
  750.   if (ROOT_INTERVAL_P (i))
  751.     {
  752.       Lisp_Object owner = (Lisp_Object) i->parent;
  753.       parent = delete_node (i);
  754.       if (! NULL_INTERVAL_P (parent))
  755.     parent->parent = (INTERVAL) owner;
  756.  
  757.       if (XTYPE (owner) == Lisp_Buffer)
  758.     XBUFFER (owner)->intervals = parent;
  759.       else if (XTYPE (owner) == Lisp_String)
  760.     XSTRING (owner)->intervals = parent;
  761.       else
  762.     abort ();
  763.  
  764.       return;
  765.     }
  766.  
  767.   parent = i->parent;
  768.   if (AM_LEFT_CHILD (i))
  769.     {
  770.       parent->left = delete_node (i);
  771.       if (! NULL_INTERVAL_P (parent->left))
  772.     parent->left->parent = parent;
  773.     }
  774.   else
  775.     {
  776.       parent->right = delete_node (i);
  777.       if (! NULL_INTERVAL_P (parent->right))
  778.     parent->right->parent = parent;
  779.     }
  780. }
  781.  
  782. /* Find the interval in TREE corresponding to the relative position
  783.    FROM and delete as much as possible of AMOUNT from that interval.
  784.    Return the amount actually deleted, and if the interval was
  785.    zeroed-out, delete that interval node from the tree.
  786.  
  787.    Note that FROM is actually origin zero, aka relative to the
  788.    leftmost edge of tree.  This is appropriate since we call ourselves
  789.    recursively on subtrees.
  790.  
  791.    Do this by recursing down TREE to the interval in question, and
  792.    deleting the appropriate amount of text. */
  793.  
  794. static int
  795. interval_deletion_adjustment (tree, from, amount)
  796.      register INTERVAL tree;
  797.      register int from, amount;
  798. {
  799.   register int relative_position = from;
  800.  
  801.   if (NULL_INTERVAL_P (tree))
  802.     return 0;
  803.  
  804.   /* Left branch */
  805.   if ((unsigned)relative_position < LEFT_TOTAL_LENGTH (tree))
  806.     {
  807.       int subtract = interval_deletion_adjustment (tree->left,
  808.                            relative_position,
  809.                            amount);
  810.       tree->total_length -= subtract;
  811.       return subtract;
  812.     }
  813.   /* Right branch */
  814.   else if ((unsigned)relative_position >= (TOTAL_LENGTH (tree)
  815.                  - RIGHT_TOTAL_LENGTH (tree)))
  816.     {
  817.       int subtract;
  818.  
  819.       relative_position -= (tree->total_length
  820.                 - RIGHT_TOTAL_LENGTH (tree));
  821.       subtract = interval_deletion_adjustment (tree->right,
  822.                            relative_position,
  823.                            amount);
  824.       tree->total_length -= subtract;
  825.       return subtract;
  826.     }
  827.   /* Here -- this node */
  828.   else
  829.     {
  830.       /* How much can we delete from this interval?  */
  831.       int my_amount = ((tree->total_length 
  832.             - RIGHT_TOTAL_LENGTH (tree))
  833.                - relative_position);
  834.  
  835.       if (amount > my_amount)
  836.     amount = my_amount;
  837.  
  838.       tree->total_length -= amount;
  839.       if (LENGTH (tree) == 0)
  840.     delete_interval (tree);
  841.       
  842.       return amount;
  843.     }
  844.  
  845.   /* Never reach here */
  846. }
  847.  
  848. /* Effect the adjustments necessary to the interval tree of BUFFER to
  849.    correspond to the deletion of LENGTH characters from that buffer
  850.    text.  The deletion is effected at position START (which is a
  851.    buffer position, i.e. origin 1). */
  852.  
  853. static void
  854. adjust_intervals_for_deletion (buffer, start, length)
  855.      struct buffer *buffer;
  856.      int start, length;
  857. {
  858.   register int left_to_delete = length;
  859.   register INTERVAL tree = buffer->intervals;
  860.  
  861.   if (NULL_INTERVAL_P (tree))
  862.     return;
  863.  
  864.   if ((unsigned)start > BEG + TOTAL_LENGTH (tree)
  865.       || (unsigned)(start + length) > BEG + TOTAL_LENGTH (tree))
  866.     abort ();
  867.  
  868.   if ((unsigned)length == TOTAL_LENGTH (tree))
  869.     {
  870.       buffer->intervals = NULL_INTERVAL;
  871.       return;
  872.     }
  873.  
  874.   if (ONLY_INTERVAL_P (tree))
  875.     {
  876.       tree->total_length -= length;
  877.       return;
  878.     }
  879.  
  880.   if ((unsigned)start > BEG + TOTAL_LENGTH (tree))
  881.     start = BEG + TOTAL_LENGTH (tree);
  882.   while (left_to_delete > 0)
  883.     {
  884.       left_to_delete -= interval_deletion_adjustment (tree, start - 1,
  885.                               left_to_delete);
  886.       tree = buffer->intervals;
  887.       if ((unsigned)left_to_delete == tree->total_length)
  888.     {
  889.       buffer->intervals = NULL_INTERVAL;
  890.       return;
  891.     }
  892.     }
  893. }
  894.  
  895. /* Make the adjustments necessary to the interval tree of BUFFER to
  896.    represent an addition or deletion of LENGTH characters starting
  897.    at position START.  Addition or deletion is indicated by the sign
  898.    of LENGTH. */
  899.  
  900. INLINE void
  901. offset_intervals (buffer, start, length)
  902.      struct buffer *buffer;
  903.      int start, length;
  904. {
  905.   if (NULL_INTERVAL_P (buffer->intervals) || length == 0)
  906.     return;
  907.  
  908.   if (length > 0)
  909.     adjust_intervals_for_insertion (buffer->intervals, start, length);
  910.   else
  911.     adjust_intervals_for_deletion (buffer, start, -length);
  912. }
  913.  
  914. /* Merge interval I with its lexicographic successor. The resulting
  915.    interval is returned, and has the properties of the original
  916.    successor.  The properties of I are lost.  I is removed from the
  917.    interval tree.
  918.  
  919.    IMPORTANT:
  920.    The caller must verify that this is not the last (rightmost)
  921.    interval. */
  922.  
  923. INTERVAL
  924. merge_interval_right (i)
  925.      register INTERVAL i;
  926. {
  927.   register int absorb = LENGTH (i);
  928.   register INTERVAL successor;
  929.  
  930.   /* Zero out this interval. */
  931.   i->total_length -= absorb;
  932.  
  933.   /* Find the succeeding interval. */
  934.   if (! NULL_RIGHT_CHILD (i))      /* It's below us.  Add absorb
  935.                       as we descend. */
  936.     {
  937.       successor = i->right;
  938.       while (! NULL_LEFT_CHILD (successor))
  939.     {
  940.       successor->total_length += absorb;
  941.       successor = successor->left;
  942.     }
  943.  
  944.       successor->total_length += absorb;
  945.       delete_interval (i);
  946.       return successor;
  947.     }
  948.  
  949.   successor = i;
  950.   while (! NULL_PARENT (successor))       /* It's above us.  Subtract as
  951.                           we ascend. */
  952.     {
  953.       if (AM_LEFT_CHILD (successor))
  954.     {
  955.       successor = successor->parent;
  956.       delete_interval (i);
  957.       return successor;
  958.     }
  959.  
  960.       successor = successor->parent;
  961.       successor->total_length -= absorb;
  962.     }
  963.  
  964.   /* This must be the rightmost or last interval and cannot
  965.      be merged right.  The caller should have known. */
  966.   abort ();
  967. }
  968.  
  969. /* Merge interval I with its lexicographic predecessor. The resulting
  970.    interval is returned, and has the properties of the original predecessor.
  971.    The properties of I are lost.  Interval node I is removed from the tree.
  972.  
  973.    IMPORTANT:
  974.    The caller must verify that this is not the first (leftmost) interval. */
  975.  
  976. INTERVAL
  977. merge_interval_left (i)
  978.      register INTERVAL i;
  979. {
  980.   register int absorb = LENGTH (i);
  981.   register INTERVAL predecessor;
  982.  
  983.   /* Zero out this interval. */
  984.   i->total_length -= absorb;
  985.  
  986.   /* Find the preceding interval. */
  987.   if (! NULL_LEFT_CHILD (i))    /* It's below us. Go down,
  988.                    adding ABSORB as we go. */
  989.     {
  990.       predecessor = i->left;
  991.       while (! NULL_RIGHT_CHILD (predecessor))
  992.     {
  993.       predecessor->total_length += absorb;
  994.       predecessor = predecessor->right;
  995.     }
  996.  
  997.       predecessor->total_length += absorb;
  998.       delete_interval (i);
  999.       return predecessor;
  1000.     }
  1001.  
  1002.   predecessor = i;
  1003.   while (! NULL_PARENT (predecessor))    /* It's above us.  Go up,
  1004.                    subtracting ABSORB. */
  1005.     {
  1006.       if (AM_RIGHT_CHILD (predecessor))
  1007.     {
  1008.       predecessor = predecessor->parent;
  1009.       delete_interval (i);
  1010.       return predecessor;
  1011.     }
  1012.  
  1013.       predecessor = predecessor->parent;
  1014.       predecessor->total_length -= absorb;
  1015.     }
  1016.  
  1017.   /* This must be the leftmost or first interval and cannot
  1018.      be merged left.  The caller should have known. */
  1019.   abort ();
  1020. }
  1021.  
  1022. /* Make an exact copy of interval tree SOURCE which descends from
  1023.    PARENT.  This is done by recursing through SOURCE, copying
  1024.    the current interval and its properties, and then adjusting
  1025.    the pointers of the copy. */
  1026.  
  1027. static INTERVAL
  1028. reproduce_tree (source, parent)
  1029.      INTERVAL source, parent;
  1030. {
  1031.   register INTERVAL t = make_interval ();
  1032.  
  1033.   bcopy (source, t, INTERVAL_SIZE);
  1034.   copy_properties (source, t);
  1035.   t->parent = parent;
  1036.   if (! NULL_LEFT_CHILD (source))
  1037.     t->left = reproduce_tree (source->left, t);
  1038.   if (! NULL_RIGHT_CHILD (source))
  1039.     t->right = reproduce_tree (source->right, t);
  1040.  
  1041.   return t;
  1042. }
  1043.  
  1044. #if 0
  1045. /* Nobody calls this.  Perhaps it's a vestige of an earlier design.  */
  1046.  
  1047. /* Make a new interval of length LENGTH starting at START in the
  1048.    group of intervals INTERVALS, which is actually an interval tree.
  1049.    Returns the new interval.
  1050.  
  1051.    Generate an error if the new positions would overlap an existing
  1052.    interval. */
  1053.  
  1054. static INTERVAL
  1055. make_new_interval (intervals, start, length)
  1056.      INTERVAL intervals;
  1057.      int start, length;
  1058. {
  1059.   INTERVAL slot;
  1060.  
  1061.   slot = find_interval (intervals, start);
  1062.   if (start + length > slot->position + LENGTH (slot))
  1063.     error ("Interval would overlap");
  1064.  
  1065.   if (start == slot->position && length == LENGTH (slot))
  1066.     return slot;
  1067.  
  1068.   if (slot->position == start)
  1069.     {
  1070.       /* New right node. */
  1071.       split_interval_right (slot, length);
  1072.       return slot;
  1073.     }
  1074.  
  1075.   if (slot->position + LENGTH (slot) == start + length)
  1076.     {
  1077.       /* New left node. */
  1078.       split_interval_left (slot, LENGTH (slot) - length);
  1079.       return slot;
  1080.     }
  1081.  
  1082.   /* Convert interval SLOT into three intervals. */
  1083.   split_interval_left (slot, start - slot->position);
  1084.   split_interval_right (slot, length);
  1085.   return slot;
  1086. }
  1087. #endif
  1088.  
  1089. /* Insert the intervals of SOURCE into BUFFER at POSITION.
  1090.  
  1091.    This is used in insdel.c when inserting Lisp_Strings into the
  1092.    buffer.  The text corresponding to SOURCE is already in the buffer
  1093.    when this is called.  The intervals of new tree are a copy of those
  1094.    belonging to the string being inserted; intervals are never
  1095.    shared.
  1096.  
  1097.    If the inserted text had no intervals associated, this function
  1098.    simply returns -- offset_intervals should handle placing the
  1099.    text in the correct interval, depending on the sticky bits.
  1100.  
  1101.    If the inserted text had properties (intervals), then there are two
  1102.    cases -- either insertion happened in the middle of some interval,
  1103.    or between two intervals.
  1104.  
  1105.    If the text goes into the middle of an interval, then new
  1106.    intervals are created in the middle with only the properties of
  1107.    the new text, *unless* the macro MERGE_INSERTIONS is true, in
  1108.    which case the new text has the union of its properties and those
  1109.    of the text into which it was inserted.
  1110.  
  1111.    If the text goes between two intervals, then if neither interval
  1112.    had its appropriate sticky property set (front_sticky, rear_sticky),
  1113.    the new text has only its properties.  If one of the sticky properties
  1114.    is set, then the new text "sticks" to that region and its properties
  1115.    depend on merging as above.  If both the preceding and succeeding
  1116.    intervals to the new text are "sticky", then the new text retains
  1117.    only its properties, as if neither sticky property were set.  Perhaps
  1118.    we should consider merging all three sets of properties onto the new
  1119.    text... */
  1120.  
  1121. void
  1122. graft_intervals_into_buffer (source, position, buffer)
  1123.      INTERVAL source;
  1124.      int position;
  1125.      struct buffer *buffer;
  1126. {
  1127.   register INTERVAL under, over, this, prev;
  1128.   register INTERVAL tree = buffer->intervals;
  1129.   int middle;
  1130.  
  1131.   /* If the new text has no properties, it becomes part of whatever
  1132.      interval it was inserted into. */
  1133.   if (NULL_INTERVAL_P (source))
  1134.     return;
  1135.  
  1136.   if (NULL_INTERVAL_P (tree))
  1137.     {
  1138.       /* The inserted text constitutes the whole buffer, so
  1139.      simply copy over the interval structure. */
  1140.       if ((unsigned)(BUF_Z (buffer) - BUF_BEG (buffer)) == TOTAL_LENGTH (source))
  1141.     {
  1142.       buffer->intervals = reproduce_tree (source, tree->parent);
  1143.       /* Explicitly free the old tree here. */
  1144.  
  1145.       return;
  1146.     }
  1147.  
  1148.       /* Create an interval tree in which to place a copy
  1149.      of the intervals of the inserted string. */
  1150.       {
  1151.     Lisp_Object buf;
  1152.     XSET (buf, Lisp_Buffer, buffer);
  1153.     tree = create_root_interval (buf);
  1154.       }
  1155.     }
  1156.   else
  1157.     if (TOTAL_LENGTH (tree) == TOTAL_LENGTH (source))
  1158.       /* If the buffer contains only the new string, but
  1159.      there was already some interval tree there, then it may be
  1160.      some zero length intervals.  Eventually, do something clever
  1161.      about inserting properly.  For now, just waste the old intervals. */
  1162.       {
  1163.     buffer->intervals = reproduce_tree (source, tree->parent);
  1164.     /* Explicitly free the old tree here. */
  1165.  
  1166.     return;
  1167.       }
  1168.     else
  1169.       /* Paranoia -- the text has already been added, so this buffer
  1170.      should be of non-zero length. */
  1171.       if (TOTAL_LENGTH (tree) == 0)
  1172.     abort ();
  1173.  
  1174.   this = under = find_interval (tree, position);
  1175.   if (NULL_INTERVAL_P (under))    /* Paranoia */
  1176.     abort ();
  1177.   over = find_interval (source, 1);
  1178.  
  1179.   /* Here for insertion in the middle of an interval.
  1180.      Split off an equivalent interval to the right,
  1181.      then don't bother with it any more.  */
  1182.  
  1183.   if ((unsigned)position > under->position)
  1184.     {
  1185.       INTERVAL end_unchanged
  1186.     = split_interval_left (this, position - under->position);
  1187.       copy_properties (under, end_unchanged);
  1188.       under->position = position;
  1189.       prev = 0;
  1190.       middle = 1;
  1191.     }
  1192.   else
  1193.     {
  1194.       prev = previous_interval (under);
  1195.       if (prev && !END_STICKY_P (prev))
  1196.     prev = 0;
  1197.     }
  1198.  
  1199.   /* Insertion is now at beginning of UNDER.  */
  1200.  
  1201.   /* The inserted text "sticks" to the interval `under',
  1202.      which means it gets those properties. */
  1203.   while (! NULL_INTERVAL_P (over))
  1204.     {
  1205.       if (LENGTH (over) + 1 < LENGTH (under))
  1206.     this = split_interval_left (under, LENGTH (over));
  1207.       else
  1208.     this = under;
  1209.       copy_properties (over, this);
  1210.       /* Insertion at the end of an interval, PREV,
  1211.      inherits from PREV if PREV is sticky at the end.  */
  1212.       if (prev && ! FRONT_STICKY_P (under)
  1213.       && MERGE_INSERTIONS (prev))
  1214.     merge_properties (prev, this);
  1215.       /* Maybe it inherits from the following interval
  1216.      if that is sticky at the front.  */
  1217.       else if ((FRONT_STICKY_P (under) || middle)
  1218.            && MERGE_INSERTIONS (under))
  1219.     merge_properties (under, this);
  1220.       over = next_interval (over);
  1221.     }
  1222.  
  1223.   buffer->intervals = balance_intervals (buffer->intervals);
  1224.   return;
  1225. }
  1226.  
  1227. /* Get the value of property PROP from PLIST,
  1228.    which is the plist of an interval.
  1229.    We check for direct properties and for categories with property PROP.  */
  1230.  
  1231. Lisp_Object
  1232. textget (plist, prop)
  1233.      Lisp_Object plist;
  1234.      register Lisp_Object prop;
  1235. {
  1236.   register Lisp_Object tail, fallback;
  1237.   fallback = Qnil;
  1238.  
  1239.   for (tail = plist; !NILP (tail); tail = Fcdr (Fcdr (tail)))
  1240.     {
  1241.       register Lisp_Object tem;
  1242.       tem = Fcar (tail);
  1243.       if (EQ (prop, tem))
  1244.     return Fcar (Fcdr (tail));
  1245.       if (EQ (tem, Qcategory))
  1246.     fallback = Fget (Fcar (Fcdr (tail)), prop);
  1247.     }
  1248.  
  1249.   return fallback;
  1250. }
  1251.  
  1252. /* Set point in BUFFER to POSITION.  If the target position is 
  1253.    before an invisible character which is not displayed with a special glyph,
  1254.    move back to an ok place to display.  */
  1255.  
  1256. void
  1257. set_point (position, buffer)
  1258.      register int position;
  1259.      register struct buffer *buffer;
  1260. {
  1261.   register INTERVAL to, from, toprev, fromprev;
  1262.   int buffer_point;
  1263.   int backwards = (position < BUF_PT (buffer)) ? 1 : 0;
  1264.   int old_position = buffer->text.pt;
  1265.  
  1266.   if (position == buffer->text.pt)
  1267.     return;
  1268.  
  1269.   /* Check this now, before checking if the buffer has any intervals.
  1270.      That way, we can catch conditions which break this sanity check
  1271.      whether or not there are intervals in the buffer.  */
  1272.   if (position > BUF_Z (buffer) || position < BUF_BEG (buffer))
  1273.     abort ();
  1274.  
  1275.   if (NULL_INTERVAL_P (buffer->intervals))
  1276.     {
  1277.       buffer->text.pt = position;
  1278.       return;
  1279.     }
  1280.  
  1281.   /* Set TO to the interval containing the char after POSITION,
  1282.      and TOPREV to the interval containing the char before POSITION.
  1283.      Either one may be null.  They may be equal.  */
  1284.   to = find_interval (buffer->intervals, position);
  1285.   if (position == BUF_BEGV (buffer))
  1286.     toprev = 0;
  1287.   else if (to->position == (unsigned)position)
  1288.     toprev = previous_interval (to);
  1289.   else
  1290.     toprev = to;
  1291.  
  1292.   buffer_point = (BUF_PT (buffer) == BUF_ZV (buffer)
  1293.           ? BUF_ZV (buffer) - 1
  1294.           : BUF_PT (buffer));
  1295.  
  1296.   /* Set FROM to the interval containing the char after PT,
  1297.      and FROMPREV to the interval containing the char before PT.
  1298.      Either one may be null.  They may be equal.  */
  1299.   /* We could cache this and save time. */
  1300.   from = find_interval (buffer->intervals, buffer_point);
  1301.   if (from->position == (unsigned)BUF_BEGV (buffer))
  1302.     fromprev = 0;
  1303.   else if (from->position == (unsigned)BUF_PT (buffer))
  1304.     fromprev = previous_interval (from);
  1305.   else if (buffer_point != BUF_PT (buffer))
  1306.     fromprev = from, from = 0;
  1307.   else
  1308.     fromprev = from;
  1309.  
  1310.   /* Moving within an interval */
  1311.   if (to == from && toprev == fromprev && INTERVAL_VISIBLE_P (to))
  1312.     {
  1313.       buffer->text.pt = position;
  1314.       return;
  1315.     }
  1316.  
  1317.   /* If the new position is before an invisible character,
  1318.      move forward over all such.  */
  1319.   while (! NULL_INTERVAL_P (to)
  1320.      && ! INTERVAL_VISIBLE_P (to)
  1321.      && ! DISPLAY_INVISIBLE_GLYPH (to))
  1322.     {
  1323.       toprev = to;
  1324.       to = next_interval (to);
  1325.       if (NULL_INTERVAL_P (to))
  1326.     position = BUF_ZV (buffer);
  1327.       else
  1328.     position = to->position;
  1329.     }
  1330.  
  1331.   buffer->text.pt = position;
  1332.  
  1333.   /* We run point-left and point-entered hooks here, iff the
  1334.      two intervals are not equivalent.  These hooks take
  1335.      (old_point, new_point) as arguments.  */
  1336.   if (! intervals_equal (from, to)
  1337.       || ! intervals_equal (fromprev, toprev))
  1338.     {
  1339.       Lisp_Object leave_after, leave_before, enter_after, enter_before;
  1340.  
  1341.       if (fromprev)
  1342.     leave_after = textget (fromprev->plist, Qpoint_left);
  1343.       else
  1344.     leave_after = Qnil;
  1345.       if (from)
  1346.     leave_before = textget (from->plist, Qpoint_left);
  1347.       else
  1348.     leave_before = Qnil;
  1349.  
  1350.       if (toprev)
  1351.     enter_after = textget (toprev->plist, Qpoint_entered);
  1352.       else
  1353.     enter_after = Qnil;
  1354.       if (to)
  1355.     enter_before = textget (to->plist, Qpoint_entered);
  1356.       else
  1357.     enter_before = Qnil;
  1358.  
  1359.       if (! EQ (leave_before, enter_before) && !NILP (leave_before))
  1360.     call2 (leave_before, old_position, position);
  1361.       if (! EQ (leave_after, enter_after) && !NILP (leave_after))
  1362.     call2 (leave_after, old_position, position);
  1363.  
  1364.       if (! EQ (enter_before, leave_before) && !NILP (enter_before))
  1365.     call2 (enter_before, old_position, position);
  1366.       if (! EQ (enter_after, leave_after) && !NILP (enter_after))
  1367.     call2 (enter_after, old_position, position);
  1368.     }
  1369. }
  1370.  
  1371. /* Set point temporarily, without checking any text properties. */
  1372.  
  1373. INLINE void
  1374. temp_set_point (position, buffer)
  1375.      int position;
  1376.      struct buffer *buffer;
  1377. {
  1378.   buffer->text.pt = position;
  1379. }
  1380.  
  1381. /* Return the proper local map for position POSITION in BUFFER.
  1382.    Use the map specified by the local-map property, if any.
  1383.    Otherwise, use BUFFER's local map.  */
  1384.  
  1385. Lisp_Object
  1386. get_local_map (position, buffer)
  1387.      register int position;
  1388.      register struct buffer *buffer;
  1389. {
  1390.   register INTERVAL interval;
  1391.   Lisp_Object prop, tem;
  1392.  
  1393.   if (NULL_INTERVAL_P (buffer->intervals))
  1394.     return current_buffer->keymap;
  1395.  
  1396.   /* Perhaps we should just change `position' to the limit. */
  1397.   if (position > BUF_Z (buffer) || position < BUF_BEG (buffer))
  1398.     abort ();
  1399.  
  1400.   interval = find_interval (buffer->intervals, position);
  1401.   prop = textget (interval->plist, Qlocal_map);
  1402.   if (NILP (prop))
  1403.     return current_buffer->keymap;
  1404.  
  1405.   /* Use the local map only if it is valid.  */
  1406.   tem = Fkeymapp (prop);
  1407.   if (!NILP (tem))
  1408.     return prop;
  1409.  
  1410.   return current_buffer->keymap;
  1411. }
  1412.  
  1413. /* Call the modification hook functions in LIST, each with START and END.  */
  1414.  
  1415. static void
  1416. call_mod_hooks (list, start, end)
  1417.      Lisp_Object list, start, end;
  1418. {
  1419.   struct gcpro gcpro1;
  1420.   GCPRO1 (list);
  1421.   while (!NILP (list))
  1422.     {
  1423.       call2 (Fcar (list), start, end);
  1424.       list = Fcdr (list);
  1425.     }
  1426.   UNGCPRO;
  1427. }
  1428.  
  1429. /* Check for read-only intervals and signal an error if we find one.
  1430.    Then check for any modification hooks in the range START up to
  1431.    (but not including) TO.  Create a list of all these hooks in
  1432.    lexicographic order, eliminating consecutive extra copies of the
  1433.    same hook.  Then call those hooks in order, with START and END - 1
  1434.    as arguments. */
  1435.  
  1436. void
  1437. verify_interval_modification (buf, start, end)
  1438.      struct buffer *buf;
  1439.      int start, end;
  1440. {
  1441.   register INTERVAL intervals = buf->intervals;
  1442.   register INTERVAL i;
  1443.   Lisp_Object hooks;
  1444.   register Lisp_Object prev_mod_hooks;
  1445.   Lisp_Object mod_hooks;
  1446.   struct gcpro gcpro1;
  1447.  
  1448.   hooks = Qnil;
  1449.   prev_mod_hooks = Qnil;
  1450.   mod_hooks = Qnil;
  1451.  
  1452.   if (NULL_INTERVAL_P (intervals))
  1453.     return;
  1454.  
  1455.   if (start > end)
  1456.     {
  1457.       int temp = start;
  1458.       start = end;
  1459.       end = temp;
  1460.     }
  1461.  
  1462.   /* For an insert operation, check the two chars around the position.  */
  1463.   if (start == end)
  1464.     {
  1465.       INTERVAL prev;
  1466.       Lisp_Object before, after;
  1467.  
  1468.       /* Set I to the interval containing the char after START,
  1469.      and PREV to the interval containing the char before START.
  1470.      Either one may be null.  They may be equal.  */
  1471.       i = find_interval (intervals, start);
  1472.  
  1473.       if (start == BUF_BEGV (buf))
  1474.     prev = 0;
  1475.       if (i->position == (unsigned)start)
  1476.     prev = previous_interval (i);
  1477.       else if (i->position < (unsigned)start)
  1478.     prev = i;
  1479.       if (start == BUF_ZV (buf))
  1480.     i = 0;
  1481.  
  1482.       if (NULL_INTERVAL_P (prev))
  1483.     {
  1484.       if (! INTERVAL_WRITABLE_P (i))
  1485.         error ("Attempt to insert within read-only text");
  1486.     }
  1487.       else if (NULL_INTERVAL_P (i))
  1488.     {
  1489.       if (! INTERVAL_WRITABLE_P (prev))
  1490.         error ("Attempt to insert within read-only text");
  1491.     }
  1492.       else
  1493.     {
  1494.       before = textget (prev->plist, Qread_only);
  1495.       after = textget (i->plist, Qread_only);
  1496.       if (! NILP (before) && EQ (before, after)
  1497.           /* This checks Vinhibit_read_only properly
  1498.          for the common value of the read-only property.  */
  1499.           && ! INTERVAL_WRITABLE_P (i))
  1500.         error ("Attempt to insert within read-only text");
  1501.     }
  1502.  
  1503.       /* Run both insert hooks (just once if they're the same).  */
  1504.       if (!NULL_INTERVAL_P (prev))
  1505.     prev_mod_hooks = textget (prev->plist, Qinsert_behind_hooks);
  1506.       if (!NULL_INTERVAL_P (i))
  1507.     mod_hooks = textget (i->plist, Qinsert_in_front_hooks);
  1508.       GCPRO1 (mod_hooks);
  1509.       if (! NILP (prev_mod_hooks))
  1510.     call_mod_hooks (prev_mod_hooks, make_number (start),
  1511.             make_number (end));
  1512.       UNGCPRO;
  1513.       if (! NILP (mod_hooks) && ! EQ (mod_hooks, prev_mod_hooks))
  1514.     call_mod_hooks (mod_hooks, make_number (start), make_number (end));
  1515.     }
  1516.   else
  1517.     {
  1518.       /* Loop over intervals on or next to START...END,
  1519.      collecting their hooks.  */
  1520.  
  1521.       i = find_interval (intervals, start);
  1522.       do
  1523.     {
  1524.       if (! INTERVAL_WRITABLE_P (i))
  1525.         error ("Attempt to modify read-only text");
  1526.  
  1527.       mod_hooks = textget (i->plist, Qmodification_hooks);
  1528.       if (! NILP (mod_hooks) && ! EQ (mod_hooks, prev_mod_hooks))
  1529.         {
  1530.           hooks = Fcons (mod_hooks, hooks);
  1531.           prev_mod_hooks = mod_hooks;
  1532.         }
  1533.  
  1534.       i = next_interval (i);
  1535.     }
  1536.       /* Keep going thru the interval containing the char before END.  */
  1537.       while (! NULL_INTERVAL_P (i) && i->position < (unsigned)end)
  1538.           ;
  1539.  
  1540.       GCPRO1 (hooks);
  1541.       hooks = Fnreverse (hooks);
  1542.       while (! EQ (hooks, Qnil))
  1543.     {
  1544.       call_mod_hooks (Fcar (hooks), make_number (start),
  1545.               make_number (end));
  1546.       hooks = Fcdr (hooks);
  1547.     }
  1548.       UNGCPRO;
  1549.     }
  1550. }
  1551.  
  1552. /* Balance an interval node if the amount of text in its left and right
  1553.    subtrees differs by more than the percentage specified by
  1554.    `interval-balance-threshold'. */
  1555.  
  1556. static INTERVAL
  1557. balance_an_interval (i)
  1558.      INTERVAL i;
  1559. {
  1560.   register int total_children_size = (LEFT_TOTAL_LENGTH (i)
  1561.                       + RIGHT_TOTAL_LENGTH (i));
  1562.   register int threshold = (XFASTINT (interval_balance_threshold)
  1563.                 * (total_children_size / 100));
  1564.  
  1565.   /* Balance within each side.  */
  1566.   balance_intervals (i->left);
  1567.   balance_intervals (i->right);
  1568.  
  1569.   if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
  1570.       && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > (unsigned)threshold)
  1571.     {
  1572.       i = rotate_right (i);
  1573.       /* If that made it unbalanced the other way, take it back.  */
  1574.       if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i)
  1575.       && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > (unsigned)threshold)
  1576.     return rotate_left (i);
  1577.       return i;
  1578.     }
  1579.  
  1580.   if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i)
  1581.       && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > (unsigned)threshold)
  1582.     {
  1583.       i = rotate_left (i);
  1584.       if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
  1585.       && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > (unsigned)threshold)
  1586.     return rotate_right (i);
  1587.       return i;
  1588.     }
  1589.  
  1590.   return i;
  1591. }
  1592.  
  1593. /* Balance the interval tree TREE.  Balancing is by weight
  1594.    (the amount of text). */
  1595.  
  1596. INTERVAL
  1597. balance_intervals (tree)
  1598.      register INTERVAL tree;
  1599. {
  1600.   register INTERVAL new_tree;
  1601.  
  1602.   if (NULL_INTERVAL_P (tree))
  1603.     return NULL_INTERVAL;
  1604.  
  1605.   new_tree = tree;
  1606.   do
  1607.     {
  1608.       tree = new_tree;
  1609.       new_tree = balance_an_interval (new_tree);
  1610.     }
  1611.   while (new_tree != tree);
  1612.  
  1613.   return new_tree;
  1614. }
  1615.  
  1616. /* Produce an interval tree reflecting the intervals in
  1617.    TREE from START to START + LENGTH. */
  1618.  
  1619. INTERVAL
  1620. copy_intervals (tree, start, length)
  1621.      INTERVAL tree;
  1622.      int start, length;
  1623. {
  1624.   register INTERVAL i, new, t;
  1625.   register int got, prevlen;
  1626.  
  1627.   if (NULL_INTERVAL_P (tree) || length <= 0)
  1628.     return NULL_INTERVAL;
  1629.  
  1630.   i = find_interval (tree, start);
  1631.   if (NULL_INTERVAL_P (i) || LENGTH (i) == 0)
  1632.     abort ();
  1633.  
  1634.   /* If there is only one interval and it's the default, return nil. */
  1635.   if ((start - i->position + 1 + length) < LENGTH (i)
  1636.       && DEFAULT_INTERVAL_P (i))
  1637.     return NULL_INTERVAL;
  1638.  
  1639.   new = make_interval ();
  1640.   new->position = 1;
  1641.   got = (LENGTH (i) - (start - i->position));
  1642.   new->total_length = length;
  1643.   copy_properties (i, new);
  1644.  
  1645.   t = new;
  1646.   prevlen = got;
  1647.   while (got < length)
  1648.     {
  1649.       i = next_interval (i);
  1650.       t = split_interval_right (t, prevlen);
  1651.       copy_properties (i, t);
  1652.       prevlen = LENGTH (i);
  1653.       got += prevlen;
  1654.     }
  1655.  
  1656.   return balance_intervals (new);
  1657. }
  1658.  
  1659. /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
  1660.  
  1661. INLINE void
  1662. copy_intervals_to_string (string, buffer, position, length)
  1663.      Lisp_Object string, buffer;
  1664.      int position, length;
  1665. {
  1666.   INTERVAL interval_copy = copy_intervals (XBUFFER (buffer)->intervals,
  1667.                        position, length);
  1668.   if (NULL_INTERVAL_P (interval_copy))
  1669.     return;
  1670.  
  1671.   interval_copy->parent = (INTERVAL) string;
  1672.   XSTRING (string)->intervals = interval_copy;
  1673. }
  1674.  
  1675. #endif /* USE_TEXT_PROPERTIES */
  1676.